package assignment1;

import java.util.LinkedList;


public class Tree234 {
	
	private Node root = new Node(); // make root node
	 
	public DataItem  find(String key)           
	{           
		Node curNode = root;           
		DataItem  childNumber = new DataItem(key);
		int indexKeyinNode = 0;
		while(true){   
			
			if((indexKeyinNode = curNode.findItem(key) ) != -1){  
				childNumber = curNode.getItem(indexKeyinNode);
				return childNumber; 
			}// found it              
			else if( curNode.isLeaf() ) 
				{
					return null;
				}                        // can't find it              
			else                                 // search deeper                 
				{curNode = getNextChild(curNode, key);}              
			}  // end while           
		}    
		
	
	  // ------------------------------------------------------------
	// insert a DataItem
	
	public void insert(PairKeyWord dValue){
		Node curNode1 = root;
		// Kiểm tra xem data có tồn tại chưa
		int indexKeyinNode = 0;
		while(true){              
			if((indexKeyinNode = curNode1.findItem(dValue.getKey()) ) != -1){  
				curNode1.getItem(indexKeyinNode).AddWord(dValue.getWord()); // Nếu key có rồi chỉ việc thêm từ mới vào
				return ; 
			}// found it              
			else if( curNode1.isLeaf() ) 
				{break;}                        // can't find it              
			else                                 // search deeper                 
				{
					curNode1 = getNextChild(curNode1, dValue.getKey());
				}              
			}  // end while           
		    
	
		// Bắt đầu thêm mới nếu như key đó chưa có trong Tree
		Node curNode = root;
		DataItem tempItem = new DataItem(dValue.getKey());
		tempItem.AddWord(dValue.getWord()); // Tạo DataItem luôn để add vào node
		
		while(true){
			if( curNode.isFull() ) // if node full,
			{
				split(curNode); // split it
				curNode = curNode.getParent(); // back up
				// search once
				curNode = getNextChild(curNode, dValue.getKey());
			} // end if(node is full)
			else if( curNode.isLeaf() ) // if node is leaf
				break; // go insert
			// node is not full, not a leaf; so go to lower level
			else
				curNode = getNextChild(curNode, dValue.getKey());
		} // end while
		curNode.insertItem(tempItem); // insert  DataItem
	} // end insert()
	// ------------------------------------------------------------
	
	
	public void split(Node thisNode) // split the node
	{
		// assumes node is full
		DataItem itemB, itemC;
		Node parent, child2, child3;
		int itemIndex;
		itemC = thisNode.removeItem(); // remove items from
		itemB = thisNode.removeItem(); // this node
		child2 = thisNode.disconnectChild(2); // remove children
		child3 = thisNode.disconnectChild(3); // from this node
		Node newRight = new Node(); // make new node
		if(thisNode==root) // if this is the root,
		{
			root = new Node(); // make new root
			parent = root; // root is our parent
			root.connectChild(0, thisNode); // connect to parent
		}
		else // this node not the root
			parent = thisNode.getParent(); // get parent
		// deal with parent
		itemIndex = parent.insertItem(itemB); // item B to parent
		int n = parent.getNumItems(); // total items?
		for(int j=n-1; j>itemIndex; j--) // move parent's
		{ // connections
			Node temp = parent.disconnectChild(j); // one child
			parent.connectChild(j+1, temp); // to the right
		}
		// connect newRight to parent
		parent.connectChild(itemIndex+1, newRight);
		// deal with newRight
		newRight.insertItem(itemC); // item C to newRight
		newRight.connectChild(0, child2); // connect to 0 and 1
		newRight.connectChild(1, child3); // on newRight
		} // end split()
		// ------------------------------------------------------------
	
	// gets appropriate child of node during search for value
		public Node getNextChild(Node theNode, String theValue)
		{
			int j;
			// assumes node is not empty, not full, not a leaf
		int numItems = theNode.getNumItems();
		for(j=0; j<numItems; j++) // for each item in node
		{ // are we less?
			if( theValue.compareTo(theNode.getItem(j).getdData()) < 0 ) // --- Lúc đầu là theNode.getItem(j).getdData())==-1
				{return theNode.getChild(j);} // return left child
		} // end for // we're greater, so
		return theNode.getChild(j); // return right child
			}
	// ------------------------------------------------------------
	
		public void displayTree()
		{
			recDisplayTree(root, 0, 0);
		}
	// ------------------------------------------------------------
	
		public static String result_display_tree ="Display tree"+ "\n \n"; 
		
		private void recDisplayTree(Node thisNode, int level,int childNumber)
		{
			//System.out.print("level="+level+" child="+childNumber+"");
			result_display_tree = result_display_tree+ thisNode.displayNode(); // display this node
			// call ourselves for each child of this node
			int numItems = thisNode.getNumItems();
			for(int j=0; j<numItems+1; j++)
			{
				Node nextNode = thisNode.getChild(j);
				if(nextNode != null)
					recDisplayTree(nextNode, level+1, j);
				else
		return;
			}
		} // end recDisplayTree()
		// -------------------------------------------------------------\
		
		
		/////////// Câu c ///////////////////////
		
		
		public Node GetLeafOfNode(Node currNode){
			if(currNode == null){return null;}
			Node childLeaf = currNode;
			while(!childLeaf.isLeaf())
			{
				if(childLeaf.getNumItems() > 0){
					childLeaf = childLeaf.getChild(0);
				}
				else{
					break;
				}
			}
			return childLeaf;
		}
		
		public int LengFromNodeToLeaf(Node currNode){
			Node childLeaf = currNode;
			int height = 0;
			while(!childLeaf.isLeaf())
			{
				if(childLeaf.getNumItems() > 0){
					childLeaf = childLeaf.getChild(0);
					height = height+1;
				}
				else{
					break;
				}
			}
			return height;
		}
		
		public String PrintPathFromNodeToLeaf(Node currNode){
			Node childLeaf = currNode;
			String result = currNode.Name()+" --- ";
			int height = 0;
			while(!childLeaf.isLeaf())
			{
				if(childLeaf.getNumItems() > 0){
					childLeaf = childLeaf.getChild(0);
					height = height+1;
					result = result+ childLeaf.Name() + " --- ";
				}
				else{
					break;
				}
			}
			return result;
		}
		
		public LinkedList<Node> ListOfPrecessor(Node currNode){
			Node parent = currNode;
			LinkedList<Node> arr_of_parent = new LinkedList<Node>();
			while(!(parent == root)){
				parent = parent.getParent();
				arr_of_parent.add(parent);
			}
			return arr_of_parent;
		}
		
		public int LengthFromNodeToRoot(Node currNode){
			Node parent = currNode;
			int height = 0;
			while(!(parent == root)){
				parent = parent.getParent();
				height = height+1;
				
			}
			return height;
		}
		
		public String PrintPathFromNodeToRoot(Node currNode){
			Node parent = currNode;
			String result = currNode.Name()+ " --- ";
			int height = 0;
			while(!(parent == root)){
				parent = parent.getParent();
				height = height+1;
				result = result + parent.Name() + " --- ";
				
			}
			return result;
		}
		
		public String FindLongestNodeFrom(Node currNode){
			
			// Các trường hợp đặc biệt
			//Key không tồn tại
			if(currNode == null){
				return "There isn't this key";
			}
			
			//
			if(root.getNumItems() == 0){// Cây chỉ có node root
				return "Longest path is zero";
			}
			
			if(currNode.IsSameNode(root)){ // currNode là node root
				
				Node _longestLeaf = GetLeafOfNode(root);
				int _longestpath = LengFromNodeToLeaf(root);
				String result_path = PrintPathFromNodeToLeaf(root);
				return "Longest node of "+ currNode.Name()+" is "+ _longestLeaf.Name()+" .The longest path is "+ _longestpath +". The path is "+result_path;
			}
			
			// Lấy tất cả các successor của Root
			LinkedList<Node> arr_successor_of_root = new LinkedList<Node>();
			arr_successor_of_root = root.ListOfSuccessor();
			
			// Trường hợp currNode là successor of root node
			if(CheckNodeIsInSetOfNode(currNode ,arr_successor_of_root)){
				Node diffcurrNode = new Node();
				for(Node n : arr_successor_of_root){
					if(!n.IsSameNode(currNode)){
						diffcurrNode = n;
						break;
					}
				}
				
				Node _longestLeaf = GetLeafOfNode(diffcurrNode);
				int _longestpath = LengFromNodeToLeaf(diffcurrNode)+2;
				String path_result = root.Name() + " ---> "+ PrintPathFromNodeToLeaf(diffcurrNode) + " ---> "+ currNode.Name() + " ---> "+ root.Name();
				return "Longest node of "+ currNode.Name()+" is "+ _longestLeaf.Name()+" .The longest path is "+ _longestpath+". The path is "+path_result;
			}
			
			// Lấy tất cả các parent của currNode
			LinkedList<Node> arr_of_parent_currNode = new LinkedList<Node>();
			arr_of_parent_currNode = ListOfPrecessor(currNode);
			
		
			
			// Lấy một successor bất kỳ của root mà ko phải là parent của currNode
			Node choseNode = new Node(); // Node này dc lấy de xét longest path
			for(Node node : arr_successor_of_root){
				if(!CheckNodeIsInSetOfNode(node, arr_of_parent_currNode)){
					choseNode = node;
					break;
				}
			}
			
			String path = "";
			// Lấy node leaf của node vừa dc chọn
			Node longestLeaf = GetLeafOfNode(choseNode);
			// Tính quãng đường từ root đến longestLeaf
			int longest1 = LengFromNodeToLeaf(choseNode)+1;
			path = "["+PrintPathFromNodeToLeaf(choseNode)+"] *** ["+ PrintPathFromNodeToRoot(choseNode)+"] *** ["+ PrintPathFromNodeToRoot(currNode)+"]";
			// Quãng đường từ root đến currNode
			int longgest2 = LengthFromNodeToRoot(currNode);
			
			int longestpath = longest1+longgest2;
			
			return "Longest node of "+ currNode.Name()+" is "+ longestLeaf.Name()+" .The longest path is "+ longestpath+". The path is "+ path;
		}
		
		private Boolean CheckNodeIsInSetOfNode(Node node , LinkedList<Node> list){
			for(Node n : list){
				if(n!=null){
					if(node.IsSameNode(n)){
						return true;
					}
				}
			}
			return false;
		}
		
		public Node GetNodeWithKey(String key){
			Node curNode = root;           
			Node returnnode = new Node();
			while(true){   
				
				if(curNode.findItem(key) != -1){  
					returnnode = curNode;
					return returnnode; 
				}// found it              
				else if( curNode.isLeaf() ) 
					{
						return null;
					}                        // can't find it              
				else                                 // search deeper                 
					{curNode = getNextChild(curNode, key);}              
				}  // end while  
		}
		
		///////// Câu b //////////////
		
		//cut from here
		public Node findNode(String key){
			Node curNode = root;
			while(true){   
				if(curNode.findItem(key) != -1){  
					return curNode; 
				}// found it              
				else if( curNode.isLeaf() ) 
					{
						return null;
					}                        // can't find it              
				else                                 // search deeper                 
					{curNode = getNextChild(curNode, key);}              
				}  // end while           
			}    
			

		public LinkedList<Node> allparentofNode(Node node){
			LinkedList<Node> list=new LinkedList<Node>();
			int i=0;
			
			Node curNode = node;
			if(curNode==root) {
				list.add(i, node);
				return list;
			}
			while(curNode!=root){
				list.add(i, curNode);
				curNode=curNode.getParent();
				i++;
			}
			list.add(i, root);
			return list;
		}
		public LinkedList<Node> shortestPath(LinkedList<Node> list1,LinkedList<Node> list2){
			LinkedList<Node> list =new LinkedList<Node>();
			int j1=0;
			int i1=0;
			int k=0;
			for(int i=0;i<list1.size();i++){
				list.add(i, list1.get(i));
				for(int j=0;j<list2.size();j++){
					
					if(list1.get(i)==list2.get(j)){
						j1=j;
						break;
					}
				}	
				if(list1.get(i)==list2.get(j1)){
					i1=i;
					break;
				}
				
			}
			
			for(int l=j1-1;l>=0;l--){
				i1++;
				list.add(i1, list2.get(l));
				
			}
			return list;
		}
		public String printShortestPath(String key1,String key2){
			String t= "";
			Node A=new Node();
			Node B=new Node();
			A=findNode(key1);
			B=findNode(key2);
			if(A==null||B==null){
				return t="One of this keys has not in any node of this tree";
			}
			if(A==B){
				return t="Two keys are in the same node";
			}
			LinkedList<Node> list1 =new LinkedList<Node>();
			LinkedList<Node> list2 =new LinkedList<Node>();
			LinkedList<Node> list =new LinkedList<Node>();
			list1=allparentofNode(A);
			list2=allparentofNode(B);
			list=shortestPath(list1, list2);
			t=t+ "Shortest path of key " + key1 + " and " + "key "+key2+ " is :\n";
			t=t+list.get(0).Name();
			for(int i=1;i<list.size();i++){
			t=t+"-->"+list.get(i).Name()+" ";
			}
			t=t+ "with length: " +list.size()+"\n";
			return t;
		} 
		// to here;
		
		  // ------------------------------------------------------------
	} // end class Tree234
	////////////////////////////////////////////////////////////////
